#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""

class Solution:
    """
    @param: nums: A list of integers
    @return: An integer denotes the sum of max two non-overlapping subarrays
    """
    def maxTwoSubArrays(self, nums):
        # write your code here
        self.n = len(nums)
        self.nums = nums
        self.ret = 0

        self.make_forward()
        self.make_reverse()
        return  self.tow_max()

    def make_forward(self):
        '''
        记录从0开始到某元素的最大值
        '''

        self.forward_end = [None] * self.n      # 以i结尾的数组的最大值
        self.forward_max = [None] * self.n      # 0---->i 之间 某连续数组的最大值, 不一定以i结尾

        first = self.nums[0]
        max_v, self.forward_end[0], self.forward_max[0]= first, first, first

        for i, v in enumerate(self.nums[1:], 1):
            new_v = self.forward_end[i-1] + v
            self.forward_end[i] = max(v, new_v)

            max_v = max(max_v, self.forward_end[i])
            self.forward_max[i] = max_v

    def make_reverse(self):
        self.inverse_end = [None] * self.n      # 以i结尾的反向数组的最大值
        self.inverse_max = [None] * self.n      # end--->i 之间 某连续数组的最大值, 不一定以i结尾, 总之最大

        last = self.nums[-1]
        max_v, self.inverse_end[-1], self.inverse_max[-1]= last, last, last
        print(max_v)

        for i, v in reversed(list(enumerate(self.nums[0:-1]))):
            new_v = self.inverse_end[i+1] + v
            self.inverse_end[i] = max(v, new_v)

            max_v = max(max_v, self.inverse_end[i])
            self.inverse_max[i] = max_v

    def tow_max(self):
        m = -999999999
        for i in range(self.n-1):
            new_m = self.forward_max[i] + self.inverse_max[i+1]
            m = max(m, new_m)

        return m


def main():
    print("start main")
    s = Solution()
    l = [4, -1, -2, 5]
    l = [1, 3, -1, 2, -1, 2]
    ret = s.maxTwoSubArrays(l)
    print('ret : %s' % ret)
    print(l)
    print(s.forward_max)
    print(s.inverse_max)

if __name__ == "__main__":
    main()
